package oj.oj_JZ31;

/**
 * JZ31 栈的压入、弹出序列
 * https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
 */
import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA.length != popA.length) {
            return false;
        }

        // 把 int[] 转成 ArrayList<Intger>
        List<Integer> pushAList = intArrayToList(pushA);
        List<Integer> popAList = intArrayToList(popA);

        // 定义栈
        Deque<Integer> stack = new LinkedList<>();

        // 遍历每个出栈序列的元素
        while (!popAList.isEmpty()) {
            // 第一个要出栈的，就是 [0] 的元素
            // 使用头删的方式，把这个元素取出来
            int popE = popAList.remove(0);
            // 检查栈顶元素是不是这个 popE
            while (stack.isEmpty() || stack.peek() != popE) {
                // 从入栈序列中取出元素，放入栈中
                // 首先应该拿入栈元素的 [0] 的元素，头删
                if (pushAList.isEmpty()) {
                    // 说明 栈顶元素 和 要出栈的元素不相等 && 没有元素可供入栈了
                    return false;
                }
                int pushE = pushAList.remove(0);
                stack.push(pushE);
            }

            // 说明下一个要出栈的元素和栈顶元素相等了
            stack.pop();    // 弹出栈顶元素，循环取检查下个要出栈的元素
        }

        return true;
    }

    private List<Integer> intArrayToList(int[] array) {
        List<Integer> ans = new ArrayList<>();
        for (int e : array) {
            ans.add(e);
        }
        return ans;
    }
}

